310. Minimum Height Trees - LeetCode Solution


DFS BFS Graph

Python Code:

class Solution:
    
    def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]:
        if n <= 2:
            return [i for i in range(n)]

        neighbors = [set() for i in range(n)]
        for start, end in edges:
            neighbors[start].add(end)
            neighbors[end].add(start)

        leaves = []
        for i in range(n):
            if len(neighbors[i]) == 1:
                leaves.append(i)

        remaining_nodes = n
        while remaining_nodes > 2:
            remaining_nodes -= len(leaves)
            new_leaves = []
            while leaves:
                leaf = leaves.pop()
                neighbor = neighbors[leaf].pop()
                neighbors[neighbor].remove(leaf)
                if len(neighbors[neighbor]) == 1:
                    new_leaves.append(neighbor)

            leaves = new_leaves

        return leaves


Comments

Submit
0 Comments
More Questions

1718C - Tonya and Burenka-179
834A - The Useless Toy
1407D - Discrete Centrifugal Jumps
1095B - Array Stabilization
291B - Command Line Arguments
1174B - Ehab Is an Odd Person
624B - Making a String
1064C - Oh Those Palindromes
1471A - Strange Partition
1746A - Maxmina
1746B - Rebellion
66C - Petya and File System
1746C - Permutation Operations
1199B - Water Lily
570B - Simple Game
599C - Day at the Beach
862A - Mahmoud and Ehab and the MEX
1525A - Potion-making
1744D - Divisibility by 2n
1744A - Number Replacement
1744C - Traffic Light
1744B - Even-Odd Increments
637B - Chat Order
546C - Soldier and Cards
18D - Seller Bob
842B - Gleb And Pizza
1746D - Paths on the Tree
1651E - Sum of Matchings
19A - World Football Cup
630P - Area of a Star